package com.zang.dp;

import java.util.Comparator;

/**
 * 完全背包问题
 * @author Cizai
 * @since 2022/11/29 20:24
 * @see <a href="https://leetcode.cn/problems/coin-change-ii/">...</a>
 **/
public class 零钱兑换II{

    public int change(int amount, int[] coins) {

        // dp[i] 表示装满容量为i的背包有多少种方法
        int[] dp = new int[amount+1];
        dp[0] = 1;
        // 注意循环背包里的物品在外边表示组合
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j<= amount; j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}
